package com.ding.practice.algorithm.leetcode.hot100;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashMap;
import java.util.List;


/**
 *
 * 力扣热题100之找到所有异位词的子串
 * @ID = 4338
 * @date 2024年07月17日16:54:49
 * 给定两个字符串 s 和 p，找到 s 中所有 p 的 异位词 的子串，返回这些子串的起始索引。不考虑答案输出的顺序。
 *
 * 异位词 指由相同字母重排列形成的字符串（包括相同的字符串）。
 *
 *
 *
 * 示例 1:
 *
 * 输入: s = "cbaebabacd", p = "abc"
 * 输出: [0,6]
 * 解释:
 * 起始索引等于 0 的子串是 "cba", 它是 "abc" 的异位词。
 * 起始索引等于 6 的子串是 "bac", 它是 "abc" 的异位词。
 *  示例 2:
 *
 * 输入: s = "abab", p = "ab"
 * 输出: [0,1,2]
 * 解释:
 * 起始索引等于 0 的子串是 "ab", 它是 "ab" 的异位词。
 * 起始索引等于 1 的子串是 "ba", 它是 "ab" 的异位词。
 * 起始索引等于 2 的子串是 "ab", 它是 "ab" 的异位词。
 *
 *
 * 提示:
 *
 * 1 <= s.length, p.length <= 3 * 104
 * s 和 p 仅包含小写字母
 */
public class FindAnagrams_438 {
    // 只能拿出官方解法了，用一个int[26]的数组去记录
    /*
    此题解法为滑动窗口，获取到子串比较简单，使用滑动窗口即可，关键点在于对子串和规定串的对比
    因为规定串为26个小写字母中的其中一个或多个，所以创建一个26int【】的数组，将每个字母出现多少次存在数组中，后将子串的数组和规定串的数组进行对比即可
     */
    public static List<Integer> findAnagrams(String s, String p) {
        List<Integer> retList = new ArrayList<>();
        if (s.length() < p.length()){
            return retList;
        }
        char[] pChars = p.toCharArray();
        char[] sChars = s.toCharArray();
        int[] pInts = new int[26];
        int[] tempInts;
        // 生成每个字母有多少个的数组
        for (char pChar : pChars){
            int pint = pChar - 'a';
            pInts[pint] ++;
        }
        int lp = 0;
        int rp = p.length() + lp;
        // 这里为右指针小于等于规定串长度，虽然小于等于，但是在取子串时不会让取到数组之外
        while (rp <= sChars.length){
            tempInts = new int[26];
            int index = lp;
            // 找到滑动窗口的值
            while (index < rp){
                int pint = sChars[index] - 'a';
                tempInts[pint] ++;
                index ++;
            }
            // 进行比较
            if (Arrays.equals(tempInts,pInts)){
                retList.add(lp);
            }
            // 串口滑动
            lp++;
            rp = p.length() + lp;
        }

        return retList;
    }


    // 这个办法使用hashmap去记录每个字母的出现次数，然后去比较，还是会超时呜呜呜。。。。。
    public static List<Integer> findAnagrams3(String s, String p) {
        List<Integer> retList = new ArrayList<>();
        if (s.length() < p.length()){
            return retList;
        }
        char[] pChars = p.toCharArray();
        char[] sChars = s.toCharArray();
        // 生成每个字母有多少个的Map
        HashMap<String,Integer> pMap = new HashMap();
        HashMap<String,Integer> tempMap = new HashMap();
        for (char pChar : pChars){
            if (pMap.containsKey(pChar+"")){
                int count = pMap.get(pChar+"");
                count ++;
                pMap.put(pChar+"",count);
            }else {
                pMap.put(pChar+"",1);
            }
        }
        int lp = 0;
        int rp = p.length() + lp;
        while (rp <= sChars.length){
            tempMap.clear();
            int index = lp;
            // 找到滑动窗口的值
            while (index < rp){
                if (tempMap.containsKey(sChars[index]+"")){
                    int count = tempMap.get(sChars[index]+"");
                    count ++;
                    tempMap.put(sChars[index]+"",count);
                }else {
                    tempMap.put(sChars[index]+"",1);
                }
                index ++;
            }
            // 进行比较
            boolean isEqual = true;
            if (tempMap.size() == pMap.size()){
                for (String pKey : pMap.keySet()){
                    if (!tempMap.containsKey(pKey)){
                        isEqual = false;
                        break;
                    }
                    if (tempMap.get(pKey) != pMap.get(pKey)){
                        isEqual = false;
                        break;
                    }
                }
            }else {
                isEqual = false;
            }
            if (isEqual){
                retList.add(lp);
            }
            lp++;
            rp = p.length() + lp;
        }

        return retList;
    }





    // 时间复杂度过不了，自己的解法，主要是对于p串进行排序，然后对于滑动到的串也进行排序，二者进行比较即可
    public static List<Integer> findAnagrams2(String s, String p) {
        List<Integer> retList = new ArrayList<>();
        if (s.length() < p.length()){
            return retList;
        }
        char[] pChars = p.toCharArray();
        char[] sChars = s.toCharArray();
        Arrays.sort(pChars);
        p = String.copyValueOf(pChars);
        int lp = 0;
        int rp = p.length() + lp;
        while (rp <= sChars.length){
            String find = "";
            int index = lp;
            // 找到滑动窗口的值
            while (index < rp){
                find = find + sChars[index];
                index ++;
            }
            char[] findChars = find.toCharArray();
            Arrays.sort(findChars);
            if (String.copyValueOf(findChars).equals(p)){
                retList.add(lp);
            }
            lp++;
            rp = p.length() + lp;
        }

        return retList;
    }

    public static void main(String[] args) {
        System.out.println(findAnagrams("aa","bb"));
    }
}
